#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<time.h>
#include<stdlib.h>

void CountSort1(int *a, int n) {
	int max = a[0], min = a[0];
	for (int i = 0; i < n; i++) {
		if (max < a[i]) {
			max = a[i];
		}
		if (min > a[i]) {
			min = a[i];
		}
	}
	int count = max - min + 1;
	int* hash = (int*)malloc(sizeof(int) * count);
	if(hash != NULL)
		memset(hash, 0, sizeof(int)* count);
	for (int i = 0; i < n; i++) {
		hash[a[i] - min]++;
	}
	int j = 0;
	for (int i = 0; i < count; i++) {
		while (hash[i]--) {
			a[j++] = i + min;
		}
	}
	free(hash);
}

void TestOP()
{
	srand(time(0));
	const int N = 10000000;
	int* a4 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; ++i)
	{
		a4[i] = rand();
	}
	int begin4 = clock();
	CountSort1(a4, N);
	int end4 = clock();
	printf("CountSort1:%d\n", end4 - begin4);
	free(a4);
}

void print(int *a, int n) {
	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);
	printf("\n");
}

void test1() {
	int a[] = { 1,2,3,5,4,6,7,0,8,9,6,9,2,3,5,6 };
	CountSort1(a, sizeof(a) / sizeof(a[0]));
	print(a, sizeof(a) / sizeof(a[0]));
}

int main() {
	//test1();
	TestOP();

	return 0;
}